Jeekr's site
0%

[SDOI2009]学校食堂 题解

Posted on Edited on

这是一道并不复杂的状压dp，隐藏在复杂的题面下面的是简单的思维。

做法

首先根据题意，一个人能不能打饭，是一个状态，所有的状态总和是\(2^n\)个，显然过于多了。然后一个什么时候打饭，只和后方的7个人有关系，所以可以考虑将当前这个人前面的所有状态压缩起来。于是设f[i][j]表示1i-1个人已经打到饭，ii+7打饭的状态是j。

再对照题目，我们还需要知道上一个打饭的人是哪一位，那加上一维，成为f[i][j][k]，k表示于i的相对位置。

然后就可以枚举每一个i,j,k了，将f[i][j][k]作为旧状态，去更新新的状态，这样也方便计算忍耐度。 我们有 对于st&1==1： \[f[i + 1][st >> 1][8 + k - 1], f[i][st][8 + k]\] 其他情况，从没有打饭的人里面，找一个打饭： \[f[i][st + (1 \lt\lt l)][8 + l], f[i][st][8 + k] + cal(i + k, i + l)\]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int a[N], b[N];
int f[N][1 << 8][16];
void chkmin(int &x, int v)
{
    x = min(x, v);
}
int cal(int old, int new_)
{
    if (old == 0)
        return 0;
    return a[old] ^ a[new_];
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {

        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i] >> b[i];
        memset(f, INF, sizeof f);
        f[1][0][8 - 1] = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int st = 0; st < 1 << 8; ++st)
            {
                for (int k = -8; k <= 7; ++k)
                // old
                {
                    if (f[i][st][8 + k] >= INF)
                        continue;
                    if (st & 1)
                        chkmin(f[i + 1][st >> 1][8 + k - 1], f[i][st][8 + k]);
                    else
                    {
                        int r = INF;
                        for (int l = 0; l <= 7; ++l)
                        {
                            if(st & (1 << l)) continue;
                            if (i + l > r)
                                break;
                            chkmin(r, i + l + b[i + l]);
                            chkmin(f[i][st ^ (1 << l)][8 + l], f[i][st][8 + k] + cal(i + k, i + l));
                        }
                    }
                }
            }
        }
        int ans = INF;
        for (int i = -8; i <= 0; ++i)
            chkmin(ans, f[n][1][8 + i]);
        cout << ans << endl;
    }
}